package _interview100;

import java.util.Random;
import java.util.random.RandomGenerator;

/**
 * 215. 数组中的第K个最大元素
 */
public class No215 {
    private int[] nums;
    private int k;

    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        this.k = k;

        return nums[divide(0, nums.length - 1)];
    }

    private int divide(int l, int r) {
        int mid = sort(l, r);

        if (mid + 1 > k) return divide(l, mid);
        else if (mid + 1 < k) return divide(mid + 1, r);
        else return mid;
    }

    private int sort(int l, int r) {
        // 固定最左值
        int position = nums[l];
        // 随机化
//        int random = (int) (Math.random() * (r - l) + l);
//        int position = nums[random];
//        nums[random] = nums[l];
//        nums[l] = position;

        int point = l;
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] > position) {
                point++;
                int temp = nums[point];
                nums[point] = nums[i];
                nums[i] = temp;
            }
        }
        nums[l] = nums[point];
        nums[point] = position;
        return point;
    }
}
